<html>
 <head>
  <link href="./leetcode-problem.css" rel="stylesheet" type="text/css">
 </head>
 <body>
  <div class="question_difficulty">
   难度：Hard
  </div>
  <div>
   <h1 class="question_title">
    99. Recover Binary Search Tree
   </h1>
   <p>
    Two elements of a binary search tree (BST) are swapped by mistake.
   </p>
   <p>
    Recover the tree without changing its structure.
   </p>
   <p>
    <strong>
     Example 1:
    </strong>
   </p>
   <pre>
<strong>Input:</strong> [1,3,null,null,2]

&nbsp;  1
&nbsp; /
&nbsp;3
&nbsp; \
&nbsp;  2

<strong>Output:</strong> [3,1,null,null,2]

&nbsp;  3
&nbsp; /
&nbsp;1
&nbsp; \
&nbsp;  2
</pre>
   <p>
    <strong>
     Example 2:
    </strong>
   </p>
   <pre>
<strong>Input:</strong> [3,1,4,null,null,2]

  3
 / \
1   4
&nbsp;  /
&nbsp; 2

<strong>Output:</strong> [2,1,4,null,null,3]

  2
 / \
1   4
&nbsp;  /
 &nbsp;3
</pre>
   <p>
    <strong>
     Follow up:
    </strong>
   </p>
   <ul>
    <li>
     A solution using O(
     <em>
      n
     </em>
     ) space is pretty straight forward.
    </li>
    <li>
     Could you devise a constant space solution?
    </li>
   </ul>
  </div>
  <div>
   <h1 class="question_title">
    99. 恢复二叉搜索树
   </h1>
   <p>
    二叉搜索树中的两个节点被错误地交换。
   </p>
   <p>
    请在不改变其结构的情况下，恢复这棵树。
   </p>
   <p>
    <strong>
     示例&nbsp;1:
    </strong>
   </p>
   <pre><strong>输入:</strong> [1,3,null,null,2]

&nbsp;  1
&nbsp; /
&nbsp;3
&nbsp; \
&nbsp;  2

<strong>输出:</strong> [3,1,null,null,2]

&nbsp;  3
&nbsp; /
&nbsp;1
&nbsp; \
&nbsp;  2
</pre>
   <p>
    <strong>
     示例&nbsp;2:
    </strong>
   </p>
   <pre><strong>输入:</strong> [3,1,4,null,null,2]

  3
 / \
1   4
&nbsp;  /
&nbsp; 2

<strong>输出:</strong> [2,1,4,null,null,3]

  2
 / \
1   4
&nbsp;  /
 &nbsp;3</pre>
   <p>
    <strong>
     进阶:
    </strong>
   </p>
   <ul>
    <li>
     使用 O(
     <em>
      n
     </em>
     ) 空间复杂度的解法很容易实现。
    </li>
    <li>
     你能想出一个只使用常数空间的解决方案吗？
    </li>
   </ul>
  </div>
 </body>
</html>